package binarySearch;

public class BinarySearch_704 {
    public int search2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;
        // 错误，假如只有一个元素，根本进不去循环
        while (left < right) {
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
                mid = (left + right) / 2;
            } else {
                left = mid + 1;
                mid = (left + right) / 2;
            }
        }
        return -1;
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // 如果设置right = length - 1，则搜索区间为[left,right]，while循环中是left <= right，循环退出条件为 left = right+1
        // 每次搜索完后都需要排除mid，搜索区间变为[left, mid-1],[mid+1, right]
        // 如果设置right = length，则搜索区间为[left, right)，while循环中left < right，退出条件为left = right
        // 每次搜索完后都需要排除mid，搜索区间变为[left, mid),[mid+1, right]
        while (left <= right) {
            // 与mid = (left + right) / 2;结果相同，但可以防止整形溢出
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
                mid = (left + right) / 2;
            } else {
                left = mid + 1;
                mid = (left + right) / 2;
            }
        }
        return -1;
    }

    public int search3(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        // 如果设置right = length - 1，则搜索区间为[left,right]，while循环中是left <= right，循环退出条件为 left = right+1
        // 每次搜索完后都需要排除mid，搜索区间变为[left, mid-1],[mid+1, right]
        // 如果设置right = length，则搜索区间为[left, right)，while循环中left < right，退出条件为left = right
        // 每次搜索完后都需要排除mid，搜索区间变为[left, mid),[mid+1, right]
        while (left < right) {
            // 与mid = (left + right) / 2;结果相同，但可以防止整形溢出
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid;
                mid = (left + right) / 2;
            } else {
                left = mid + 1;
                mid = (left + right) / 2;
            }
        }
        return -1;
    }

}
